package cn.zyl.demo.java.sort;

/**
 * InsertSort 类说明: 插入排序
 * -----------------------------------------------------------------------------------
 * <p>插入排序的代码实现没有冒泡排序和选择排序简单粗暴，但原理应该是最容易理解的，只要打过扑克牌的人都懂</p>
 * <p>插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入</p>
 * <p>插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入</p>
 * @author wsz
 * @version v1.0
 * @date 2020-08-13
 */
public class InsertSort extends AbstractArraySortSimple{
    /**
     * 排序接口
     * <p>
     *     算法步骤<br>
     *     1.将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。<br>
     *     2.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
     *     （如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
     * </p>
     * @param sourceArray 待排序数组
     * @param order       排序方式，(默认)升序 true；降序 false
     * @return 排序后的数组
     * @throws Exception 异常信息
     */
    @Override
    public Integer[] sort(Integer[] sourceArray, Boolean order) throws Exception {
        Integer[] arr = copyArray(sourceArray);
        //记录要插入的数据；从已经排序的序列最右边的开始比较，找到比其小的数
        int tmp,index;
        start();
        //从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = N_0,len = arr.length; i < len; i++) {
            tmp = arr[i];
            index = i;
            if(order){
                //升序
                while (index > N_0 && tmp < arr[index - N_1]){
                    arr[index] = arr[index - N_1];
                    index --;
                }
            }else {
                //降序
                while (index > N_0 && tmp > arr[index - N_1]) {
                    arr[index] = arr[index - N_1];
                    index--;
                }
            }
            // 存在比其小/大的数，插入
            if(index != i){
                addOne();
                arr[index] = tmp;
            }
        }
        end();
        return arr;
    }
    public static void main(String[] args) {
        int len =15,max=100;
        //待排序数组初始化
        Integer[] arr = randomArray(len,max);
        AbstractArraySortSimple sort = new InsertSort();
        try {
            System.out.println("升序操作");
            printArray(sort.sort(arr, true));
            System.out.println("降序降序");
            printArray(sort.sort(arr, false));
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}
